//
// Created by yewei on 2025/4/29.
//
#include<stdio.h>
#include<math.h>
#include<iostream>

using namespace std;

#define N 6
#define maxT 1000
int c[N][maxT] = {0};

int Calculate_Max_Value(int v[N], int w[N], int i, int j) {
    int temp = 0;
    if (c[i][j] != -1) {
        return c[i][j]; //1
    }
    if (i == 0 || j == 0) {
        c[i][j] = 0;
    } else {
        c[i][j] = Calculate_Max_Value(v, w, i - 1, j);
        if (j > w[i] && i > 0) { //2
            temp = Calculate_Max_Value(v, w, i - 1, j - w[i]) + v[i]; //3
            if (c[i][j] < temp) {
                c[i][j] = temp; //4
            }
        }
    }
    return c[i][j];
}

int Memorized_Knapsack(int v[N], int w[N], int T) {
    int i;
    int j;
    for (i = 0; i < N; i++) {
        for (j = 0; j <= T; j++) {
            c[i][j] = -1;
        }
    }
    return Calculate_Max_Value(v, w, N - 1, T);
}

int main() {
    int v[N] = {0, 1, 6, 18, 22, 28};
    int w[N] = {0, 1, 2, 5, 6, 7};
    int T = 11;
    cout << Memorized_Knapsack(v, w, T);

    return 0;
}
